public class Leet1370 {
    public static void main(String[] args) {
        System.out.println(sortString("rat"));
    }
    static public String sortString(String s) {
        int[] num = new int[26];
        for (char c : s.toCharArray()) {
            num[c-'a']++;
        }
        StringBuilder sb = new StringBuilder();
        int n = s.length();
        while(n!=0) {
            for (int i = 0; i < 26; i++) {
                if (num[i] == 0)
                    continue;
                sb.append((char) ('a' + i));
                num[i]--;
                n--;
            }
            for (int i = 25; i >= 0; i--) {
                if (num[i] == 0)
                    continue;
                sb.append((char) ('a' + i));
                num[i]--;
                n--;
            }
        }
        return sb.toString();
    }
}
